﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DirectedGraphCycle
{
    class FindAllUnDirectedCycle : FindAllCycle
    {
        public class UndirectedCycle : Cycle
        {
            public UndirectedCycle(List<int> vertexes) : base(vertexes) { }

            protected override Direction ChooseDirection(int indexMin)
            {
                int indexLeft = indexMin == 0 ? Vertexes.Count : indexMin - 1;
                int indexRight = indexMin == Vertexes.Count - 1 ? 0 : indexMin + 1;
                if (Vertexes.Count > 2 && Vertexes[indexLeft] < Vertexes[indexRight])
                    return Direction.LEFT;
                return Direction.RIGHT;
            }
        }

        public FindAllUnDirectedCycle()
        {
        }

        protected override void addToAdjMatrix(int v1, int v2)
        {
            adjacencyListOriginal[v1].Add(v2);
            if (v1 != v2)
                adjacencyListOriginal[v2].Add(v1);
        }

        public override List<Cycle> getAllCycles()
        {
            this.numOfCycle = 0;
            this.displayLength = 0;
            this.cycles = new List<Cycle>(MAX_WRITE_ATIME);
            this.blocked = new bool[this.numNodes];
            this.B = new List<int>[this.numNodes];
            this.stack = new List<int>(this.adjacencyListOriginal.Length);
            StrongConnectedComponents sccs = new StrongConnectedComponents(this.adjacencyListOriginal);
            int s = 0;

            while (true)
            {
                SCCResult sccResult = sccs.getStrongConnectedComponent(s);
                if (sccResult != null && sccResult.getAdjList() != null)
                {
                    ArrayList[] scc = sccResult.getAdjList();
                    s = sccResult.getLowestNodeId();
                    for (int j = 0; j < scc.Length; j++)
                    {
                        if ((scc[j] != null) && (scc[j].Count > 0))
                        {
                            this.blocked[j] = false;
                            this.B[j] = new List<int>();
                        }
                    }

                    this.circuit(s, s, scc);
                    s++;
                }
                else
                {
                    break;
                }
            }

            PrintAPart();
            return cycles;
        }

        private bool circuit(int v, int s, ArrayList[] adjListGraph)
        {
            bool f = false;
            this.stack.Add(v);
            this.blocked[v] = true;

            for (int i = 0; i < adjListGraph[v].Count; i++)
            {
                int w = (int)adjListGraph[v][i];

                if (w == s)
                {
                    if (stack.Count > 1)
                        this.cycles.Add(NewCycle(stack));
                    if (this.cycles.Count >= MAX_WRITE_ATIME)
                        PrintAPart();
                    f = true;
                }
                else if (!this.blocked[w])
                {
                    if (this.circuit(w, s, adjListGraph))
                    {
                        f = true;
                    }
                }
            }

            if (f)
            {
                this.unblock(v);
            }
            else
            {
                for (int i = 0; i < adjListGraph[v].Count; i++)
                {
                    int w = (int)adjListGraph[v][i];
                    if (!this.B[w].Contains(v))
                    {
                        this.B[w].Add(v);
                    }
                }
            }

            this.stack.Remove(v);

            return f;
        }

        private void unblock(int u)
        {
            this.blocked[u] = false;
            while (B[u].Count > 0)
            {
                int w = (int)B[u][0];
                B[u].RemoveAt(0);
                if (this.blocked[w])
                {
                    this.unblock(w);
                }
            }
        }

        protected override FindAllCycle.Cycle NewCycle(List<int> vertexes)
        {
            return new UndirectedCycle(vertexes);
        }
    }

}
